package problem21_Merge_Two_Sorted_Lists;

public class MySolution {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
		
		public String toString(){
			return val+"";
		}
	}

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode dummy=new ListNode(Integer.MIN_VALUE);
		dummy.next=l1;
		ListNode first=dummy,second=l1,third=l2;
		while(second!=null||third!=null){
			if(second==null){ first.next=third;break;}
			if(third==null)break;
			if(first.val<=third.val&&second.val>third.val){
				ListNode tmp=third;
				first.next=tmp;
				tmp.next=second;
				third=third.next;
				first=first.next;
			}else{
				first=first.next;
				second=second.next;
			}
		}
		return dummy.next;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().mergeTwoLists(new MySolution().new ListNode(2),new MySolution().new ListNode(1)));
	}
}
